package com.practice.niuke.new_direct_practice.class13;

import java.util.TreeSet;

/**
 * 给定一个一维数组matrix，再给定一个k值。返回累加和小于等于k，但是离k最近的子
 * 数组累加和。
 */
public class Code03_MaxSubArraySumLessOrEqualK {
	// arr中的数字，有正，有负，有0
	// 请返回arr中，求个子数组的累加和，是<=K的，并且是最大的。
	// 返回这个最大的累加和
	public static int getMaxLessOrEqualK(int[] arr, int K) {
		TreeSet<Integer> set = new TreeSet<Integer>();
		// 一个数也没有的前缀累加和为0
		set.add(0);
		// 最终用来记录<=K的离K最近的累加和
		int max = Integer.MIN_VALUE;
		// sum负责记录0...i位置的累加和
		int sum = 0;
		// 每一步的i，都求子数组必须以i结尾的情况下，求个子数组的累加和，是<=K的，并且是最大的
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i]; // sum -> arr[0..i];
			if (set.ceiling(sum - K) != null) {
				// 如果set中存在>=sum-k的离sum-k最近的值，sum - set.ceiling(sum - K)就是<=K离K最近的数
				max = Math.max(max, sum - set.ceiling(sum - K));
			}
			set.add(sum); // 当前的前缀和加入到set中去
		}
		return max;

	}

}
